The concept of using quantum systems to represent and process information has received increasing attention as researchers begin to recognize the theoretical capabilities of such systems. A quantum computer would be able to solve certain problems, such as the factoring of large numbers, much more rapidly than a classical computer. For example, a quantum computing algorithm has been proposed for finding prime factors in polynomial time instead of exponential time, as required by classical approaches. See P. Shor, in Proc. 35th Ann. Symp. on Found. of Comp. Sci. at 124 (1994). Also, according to Grover's algorithm, the time required for retrieval of a record from an unsorted database of r records by a quantum computer scales as .sqroot.r rather than as r, required in deterministic classical computation.
These possibilities have energized the search for practical ways to construct quantum information processors. The difficulties, which are substantial, arise from the nature of quantum systems. A conventional digital computer operates on bits representing classical Boolean states--binary zeroes and ones--and after each computational step, the computer has a definite, exactly measurable state. The state of a quantum computer, by contrast, is described by a wave function or a state in a potentially infinitely large Hilbert space that is indeterminate in the classical sense; it is this indeterminacy that gives rise to the capabilities that characterize quantum computing, but also to the difficulty of realizing practical systems.
In particular, quantum systems exhibit the properties of superposition and entanglement, which are manifested in non-classical correlations. The property of superposition allows a quantum computer to exist in an arbitrary complex linear combination of classical Boolean states, which evolve in parallel according to a unitary transformation. Entanglement prevents some definite states of a complete quantum system from corresponding to definite states of its parts. Thus, the quantum analog to a classical computer would replace two-state Boolean bits with "qubits," which represent two-state quantum systems. A qubit can represent the two classical binary states (e.g., by a fixed pair of orthogonal quantum states), but also entangled states in which neither qubit by itself has a definite state. As a result, while the state (i.e., contents) of an k-bit register in a classical computer is completely specified by k Boolean values, a k-qubit register requires 2.sup.k values; as the number of qubits increases, therefore, exponentially more values are required to specify their state.
Unfortunately, the quantum states and their correspondences that are necessary for computation are not easily manipulated and maintained under normal environmental conditions. For example, quantum states easily "decohere" (that is, become randomized as a result of entanglement with the environment). Yet a quantum computer must not only exhibit the nonlinear interactions and persistence of states necessary for computation and its readout, but also facilitate control or manipulation of those interactions by external influence-all without strong coupling to the environment.
Because of the apparent tension between these requirements, quantum computation efforts to date have emphasized isolating a small number of individual quantum degrees of freedom in microscopic systems based on trapped ions (Cirac et al., Phys. Rev. Lett. 74:4091 1995!; Monroe et al., Phys. Rev. Lett. 75:4714 1995!), quantum dots (Bandyopadhyay et al., Jap. J. Appl. Phys. 35:3350 1996!), and cavity quantum electrodynamics (Domokos et al., Phys. Rev. Lett. 52:3554 1995!; Turchette et al., Phys. Rev. Lett. 75:4710 1995!; Chuang et al., Phys. Rev. A 52:3489 1995!). In addition to their various theoretical drawbacks--for example, scale-up to larger systems--such systems require enormous technical sophistication and expense for operation and maintenance.
An alternative approach, suggested but never successfully implemented, involves the use of nuclear magnetic resonance (NMR) to modify the spin states of a microscopic system of spins, relying on nonlinear interactions among the spins for computational operations; see, e.g., DiVencenzo, Phys. Rev. B 50:1015 (1995). The approach is attractive because in general spin-lattice relaxation times for spin states can be very long, up to thousands of seconds, because the nuclei are very well screened from the environment. Moreover, known multiple-pulse resonance techniques (of the kind routinely used to determine molecular structure) probe complex networks of spin interactions, providing just the sorts of manipulations necessary to achieve computation. Unfortunately, the basic requirements for quantum computation by this approach--preparation of a system with a desired initial condition, the ability to address individual spins to implement a given algorithm, and the capacity for readout of results--pose the same difficulties in an NMR environment as in other environments, since microscopic NMR systems of this type are highly thermalized. It is difficult, for example, to address the quantum states of individual molecules in such a system. At the same time, attempts to modify the system itself (e.g., by adding special spins for input and output) are difficult to accomplish with the precision necessary for reliable computation.